package poo.util;
import java.util.*;
import poo.grafo.*;

public final class Grafi{
	private Grafi(){}

	public static <N> void visitaInAmpiezza( Grafo<N> g, N u, LinkedList<N> lista ){
		if( g==null || !g.esisteNodo(u) )
			throw new IllegalArgumentException();
		Set<N> visitato=new HashSet<N>();
		visitaInAmpiezza(g,u,visitato,lista);
	}//visitaInAmpiezza

	private static <N> void visitaInAmpiezza( Grafo<N> g, N u, Set<N> visitato, LinkedList<N> lista ){
		//breadth-first visit
		LinkedList<N> coda=new LinkedList<N>(); //coda di nodi pending gia' visitati
		coda.addLast(u);
		lista.addLast(u); //"visita" u
		visitato.add(u); //"marca" u come visitato
		while( !coda.isEmpty() ){
			N x=coda.removeFirst();
			Iterator<? extends Arco<N>> it=g.adiacenti(x);
			while( it.hasNext() ){
				N nodoAdiacente=it.next().getDestinazione();
				if( !visitato.contains(nodoAdiacente) ){
					coda.addLast( nodoAdiacente );
					lista.addLast( nodoAdiacente );
					visitato.add(nodoAdiacente);
				}
			}
		}
	}//visitaInAmpiezza

	public static <N> void visitaInProfondita( Grafo<N> g, N u, LinkedList<N> lista ){
		if( g==null || !g.esisteNodo(u) )
			throw new IllegalArgumentException();
		Set<N> visitato=new HashSet<N>();
		visitaInProfondita(g,u,visitato,lista);
	}//visitaInProfondita

	private static <N> void visitaInProfondita( Grafo<N> g, N u, Set<N> visitato, LinkedList<N> lista ){
		//depth-first visit
		lista.addLast(u);
		visitato.add(u);
		Iterator<? extends Arco<N>> it=g.adiacenti(u);
		while( it.hasNext() ){
			N nodoAdiacente=it.next().getDestinazione();
			if( !visitato.contains(nodoAdiacente) )
				visitaInProfondita(g,nodoAdiacente,visitato,lista);
		}
	}//visitaInProfondita

	public static <N> Grafo<N> raggiungibilita( Grafo<N> g ){
		Grafo<N> grafoR=g.copia();
		//genera tutti i percorsi di lunghezza k;
		//k=1 indica i percorsi unitari, cioe' gli archi,
		//gia' presenti in grafoR per costruzione
		for( int k=2; k<g.numNodi(); k++ ){
			for( N i: g )
				for( N j: g )
					for( N m: g )
						if( grafoR.esisteArco(i,m) && g.esisteArco(m,j) )
							grafoR.insArco(i,j);
		}
		return grafoR;
	}//raggiungibilita

	public static <N> int componentiConnesse( GrafoNonOrientato<N> g ){
		Set<N> visitato=new HashSet<N>();
		LinkedList<N> fittizia=new LinkedList<N>();
		int ncc=0;
		for(N u: g){
			if( !visitato.contains(u) ){
				ncc++;
				visitaInAmpiezza(g,u,visitato,fittizia);
			}
		}
		return ncc;
	}//componentiConnesse

	public static <N> boolean aciclico( GrafoOrientato<N> g ){
		//Si verifica se il grafo e' riducibile. Se si, esso e' aciciclo.
		//Si parte dai nodi con grado di entrata 0 e si mettono in una coda dei pending.
		//Ripetutamente, si estrae un nodo dalla coda. Lo si "elimina" logicamente,
		//quindi si eliminano gli archi ai relativi nodi adiacenti e nel contempo
		//si decrementa il grado di entrata di
		//ogni nodo adiacente. Ogni nuovo nodo con grado di entrata 0
		//viene inserito nella coda. Si ripete sino a che la coda dei pending
		//si svuota. A fine algoritmo, se tutti i nodi sono stati rimossi
		//il grafo e' aciciclo, altrimenti e' ciclico.
		Set<N> rimossi=new HashSet<N>(); //collezione dei nodi "rimossi"
		Map<N,Integer> gradoEntrata=new HashMap<N,Integer>();
		LinkedList<N> daRimuovere=new LinkedList<N>(); //coda "pending"
		for( N u: g ){
			int gE=g.gradoEntrata(u);
			gradoEntrata.put( u, gE );
			if( gE==0 ) daRimuovere.addLast(u);
		}
		//la coda daRimuovere contiene nodi con grado di entrata 0
		while( !daRimuovere.isEmpty() ){
			N nodo=daRimuovere.removeFirst();
			rimossi.add(nodo); //rimozione logica di nodo
			Iterator<? extends Arco<N>> it=g.adiacenti(nodo);
			//si decrementa il grado di entrata di ogni nodo adiacente ad n
			while( it.hasNext() ){
				N destinazione=it.next().getDestinazione();
				gradoEntrata.put(destinazione,gradoEntrata.get(destinazione)-1);
				if( gradoEntrata.get(destinazione)==0 )
					daRimuovere.addLast( destinazione );
			}
		}
		//si ritorna true se rimossi contiene tutti i nodi
		for( N u: g )
			if( !rimossi.contains(u) ) return false;
		return true;
	}//aciclico

	public static void main( String[] args ){
		GrafoOrientato<Integer> g=new GrafoOrientatoImpl<Integer>();
		//GrafoNonOrientato<Integer> g=new GrafoNonOrientatoImpl<Integer>();
		//nel caso di grafo non orientato, commentare la verifica di aciclico
		g.insNodo(1);
		g.insNodo(2);
		g.insNodo(3);
		g.insNodo(4);
		g.insNodo(5);
		g.insNodo(6);
		g.insNodo(7);
		g.insArco(1,2);
		g.insArco(1,3);
		g.insArco(2,4);
		g.insArco(3,5);
		g.insArco(4,5);
		g.insArco(5,2);
		g.insArco(5,3);
		g.insArco(4,6);
		g.insArco(7,6);

		GrafoOrientato<Integer> ge=new GrafoOrientatoImpl<Integer>();
		ge.insNodo(5);
		ge.insNodo(6);
		ge.insNodo(7);
		ge.insNodo(1);
		ge.insNodo(2);
		ge.insNodo(3);
		ge.insNodo(4);
		ge.insArco(1,3);
		ge.insArco(1,2);
		ge.insArco(4,6);
		ge.insArco(2,4);
		ge.insArco(3,5);
		ge.insArco(4,5);
		ge.insArco(5,3);
		ge.insArco(5,2);
		ge.insArco(7,6);
		System.out.println("g==ge ? "+ g.equals(ge));
		System.out.println("g.hashCode()="+g.hashCode()+" ge.hashCode()="+ge.hashCode());

		System.out.println(g);
		LinkedList<Integer> lis=new LinkedList<Integer>();
		visitaInAmpiezza( g, 1, lis );
		System.out.println("Visita in ampiezza: "+lis);
		lis.clear();
		visitaInProfondita( g, 1, lis );
		System.out.println("Visita in profondita': "+lis);
		System.out.println();
		System.out.println("Grafo aciclico ? "+aciclico(g));
		Grafo<Integer> gR=raggiungibilita(g);
		System.out.println("Grafo di raggiungibilita'");
		System.out.println(gR);
		System.out.println("Rimuovo l'arco <2,4>");
		g.rimuoviArco(2,4);
		System.out.println(g);
		gR.clear();
		gR=raggiungibilita(g);
		System.out.println("Nuovo grafo di raggiungibilita");
		System.out.println(gR);

		System.out.println();
		g.insArco(2,4); //ricomposizione grafo iniziale
		System.out.println(g);
		System.out.println("Test rimuoviNodo 5");
		g.rimuoviNodo(5);
		System.out.println(g);
		System.out.println("Grafo ricomposto");
		g.insNodo(5); g.insArco(5,2); g.insArco(5,3);
		g.insArco(4,5); g.insArco(3,5);
		System.out.println(g);
		System.out.println("Test rimozione nodo 5 con iteratore");
		Iterator<Integer> it=g.iterator();
		while( it.hasNext() ){
			int x=it.next();
			if(x==5){
				it.remove();
				break;
			}
		}
		System.out.println("Grafo dopo la rimozione del nodo 5");
		System.out.println(g);
	}//main

}//Grafi
